# !/usr/bin/env python
# -*- coding: utf-8 -*-

# 红黑树

# 所有的节点不是黑色的就是红色的
# 根节点是黑色的
# 所有叶子节点是黑色的(此处的叶子结点指的是空结点)
# 从每个叶子到根的所有路径上不能有两个连续的红色结点
# 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

class RedBlackTree:
    left = None
    right = None
    parent = None
    is_black = True
    val = None

    def __init__(self, val, is_black=True):
        super().__init__()
        self.val = val
        self.is_black = is_black

    def __str__(self):
        left_str = "\"\""
        right_str = "\"\""
        color = "red"
        if self.is_black:
            color = "black"
        parent_val = -1
        if self.parent is not None:
            parent_val = self.parent.val
        if self.left is not None:
            left_str = self.left.__str__()
        if self.right is not None:
            right_str = self.right.__str__()
        return '{"val":%d, "parent": %d, "left":%s, "right":%s, "color": \"%s\"}' \
               % (self.val, parent_val, left_str, right_str, color)

    def height(self):
        lh = 0
        rh = 0
        if self.left is None or self.right is None:
            return 1
        if self.left is not None:
            lh = self.left.height()
        if self.right is not None:
            rh = self.right.height()
        return max(lh, rh) + 1

    def insert(self, val):
        if self.val == val:
            return self
        cur_node = RedBlackTree(val, False)
        if val > self.val:
            if self.right is None:
                self.right = cur_node
                cur_node.parent = self
            else:
                self.right.insert(val)
                if not self.is_black:
                    self.change_color(cur_node)

        else:
            if self.left is None:
                self.left = cur_node
                cur_node.parent = self
            else:
                self.left.insert(val)
                if not self.is_black:
                    self.change_color(cur_node)
        return self

    def change_color(self, cur_node):
        cur_parent = cur_node.parent
        while cur_parent is not None:
            if cur_parent.right is not None:
                cur_parent.right.is_black = not cur_parent.right.is_black
            cur_parent.is_black = not cur_parent.is_black
            cur_parent = cur_parent.parent


if __name__ == '__main__':
    root = RedBlackTree(7, True).insert(5).insert(12).insert(10).insert(15).insert(11)
    print(root)
